import java.util.*;

public class Test {
    //题目1： 从前序与中序遍历序列构造二叉树
    int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildSubTree(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildSubTree(int[] preorder, int[] inorder, int start, int end){
        if(start > end){
            return null;
        }
        int val = preorder[i];
        i++;
        TreeNode node = new TreeNode(val);
        int index = findIndex(val, inorder, start, end);

        node.left = buildSubTree(preorder, inorder, start, index - 1);
        node.right = buildSubTree(preorder, inorder, index + 1, end);
        return node;
    }

    private int findIndex(int key, int[] inorder, int start, int end){
        for(int i = start; i <= end; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    // 题目2： 从中序与后序遍历序列构造二叉树
    int j ;
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        j = postorder.length - 1;
        return buildSubTree1(inorder, postorder, 0, inorder.length - 1);
    }

    private TreeNode buildSubTree1(int[] inorder, int[] postorder, int start, int end){
        if(start > end){
            return null;
        }

        int val = postorder[j];
        j--;

        TreeNode node = new TreeNode(val);
        int index = findIndex(inorder, start, end, val);

        node.right = buildSubTree1(inorder, postorder, index + 1, end);
        node.left = buildSubTree1(inorder, postorder, start, index - 1);
        return node;
    }

    private int findIndex(int[] inorder, int start,int end,int key){
        for(int i = start; i <= end; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    // 题目3：把二叉搜索树转换为累加树
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return root;
        }

        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }

    // 迭代写法
    public TreeNode convertBST1(TreeNode root) {
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.right;
            }

            node = stack.pop();
            sum += node.val;
            node.val = sum;
            node = node.left;
        }
        return root;
    }

    // 题目4：两棵二叉搜索树中的所有元素
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();

        while(root1 != null || root2 != null || !stack1.isEmpty()|| !stack2.isEmpty()){
            while(root1 != null){
                stack1.push(root1);
                root1 = root1.left;
            }

            while(root2 != null){
                stack2.push(root2);
                root2 = root2.left;
            }

            if(stack1.isEmpty()){
                list.add(stack2.peek().val);
                root2 = stack2.pop().right;
                continue;
            }

            if(stack2.isEmpty()){
                list.add(stack1.peek().val);
                root1 = stack1.pop().right;
                continue;
            }

            if(stack1.peek().val < stack2.peek().val){
                list.add(stack1.peek().val);
                root1 = stack1.pop().right;
            }else{
                list.add(stack2.peek().val);
                root2 = stack2.pop().right;
            }
        }
        return list;
    }

    // 题目5：数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> q = new PriorityQueue<>(k);
        for(int i = 0; i < k; i++){
            q.add(nums[i]);
        }

        for(int i = k ; i < nums.length; i++){
            if(nums[i] > q.peek()){
                q.poll();
                q.add(nums[i]);
            }
        }

        return q.poll();
    }

    // 题目6：最小K个数
    class NumCom implements Comparator<Integer>{
        @Override
        public int compare(Integer a, Integer b){
            return b - a;
        }
    }
    public int[] smallestK(int[] arr, int k) {
        int[] nums = new int[k];
        if(arr == null || k == 0){
            return nums;
        }
        NumCom numCom = new NumCom();
        Queue<Integer> q = new PriorityQueue<>(numCom);
        for(int i = 0; i < k; i++){
            q.add(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            if(arr[i] < q.peek()){
                q.poll();
                q.add(arr[i]);
            }
        }
        for(int i = 0; i < k; i++){
            nums[i] = q.poll();
        }
        return nums;
    }

    // 题目7：第三大的数
    // 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
    // 若 第三大的数不存在，不能是重复的！, 则返回最大的数

    public int thirdMax(int[] nums) {
        long a = Long.MIN_VALUE;
        long b = Long.MIN_VALUE;
        long c = Long.MIN_VALUE;

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > a){
                c = b;
                b = a;
                a = nums[i];
            }else if(a > nums[i] && nums[i] > b){
                c = b;
                b = nums[i];
            }else if(b > nums[i] && nums[i] > c){
                c = nums[i];
            }
        }

        return (int)(c == Long.MIN_VALUE ? a : c);
    }

    // 题目8：最接近原点的 K 个点
    class Cmp implements Comparator<int[]>{
        @Override
        public int compare(int[] arr1, int[] arr2){
            return arr2[0] - arr1[0];
        }
    }
    public int[][] kClosest(int[][] points, int k) {
        if(k == points.length){
            return points;
        }
        // k < points.length
        Cmp cmp = new Cmp();
        Queue<int[]> q = new PriorityQueue<>(cmp);
        for(int i = 0; i < k; i++){
            q.add(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
        }

        for(int i = k; i < points.length; i++){
            int temp = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if(temp < q.peek()[0]){
                q.poll();
                q.add(new int[]{temp,i});
            }
        }

        int[][] ans = new int[k][2];

        for(int i = 0; i < k; i++){
            ans[i] = points[q.poll()[1]];
        }

        return ans;
    }





}
